\section{The two-hop walk: Discovery through pull}
\label{sec:2hop-10p}
In this section, we analyze the two-hop walk process on undirected
connected graphs, which is described by the following simple
iteration: In each round, for each node $u$, we add edge $(u,w)$
where $w$ is drawn uniformly at random from $\nei{t}{1}{v}$, where $v$
is drawn uniformly at random from $\nei{t}{1}{u}$.  The two-hop walk
yields the following pull-based resource discovery protocol.  In each
round, each node $u$ contacts a random neighbor $v$, receives the
identity of a random neighbor $w$ of $v$, and sends its identity to
$w$.  The main result of this section is that the two-hop walk process
transforms an arbitrary connected $n$-node graph to a complete graph
in $O(n \log^2 n)$ rounds with high probability.  We also establish an
$\Omega(n\log n)$ lower bound on the two-hop walk for almost all
$n$-node graphs.

As for the triangulation process, we establish the $O(n \log^2 n)$
upper bound by showing that the minimum degree of the graph increases
by a constant factor (or equals $n-1$) in $O(n \log n)$ rounds with
high probability.  For analyzing the growth in the degree of a node
$u$, we consider two overlapping cases.  The first case is when the
two-hop neighborhood of $u$ is not too large, i.e., $|\nei{t}{2}{u}| <
\md{0}/2$, and the second is when the two-hop neighborhood of $u$ is
not too small, i.e., $|\nei{t}{2}{u}| \ge \md{0}/4$.  The proofs of
the following three claims that establish the upper bound are deferred
to Appendix~\ref{app:2hop}.

\begin{lemma}[{\bf When the two-hop neighborhood is not too large}]
\label{lem:mingrowth-1-10p}
There exists $T=O(n\log n)$ such that either $\abs{\nei{T}{2}{u}} \ge
\md{0}/2$ or $\dg{T}{u} \ge \min\cub{2\md{0},n-1}$ with probability at
least $1-1/n^2$.
\end{lemma}


\begin{lemma}[{\bf When the two-hop neighborhood is not too small}]
\label{lem:mingrowth-2-10p}
There exists $T=O(n\log n)$ such that either $\abs{\nei{T}{2}{u}} <
\md{0}/4$ or $\dg{T}{u} \ge \min\cub{(1+1/8)\md{0},n-1}$, with probability at least $1-1/n^2$.
\end{lemma}

\begin{theorem}[{\bf Upper bound for two-hop walk process}]
\label{thm:graph+randwalk-10p}
For connected undirected graphs, the two-hop walk process completes in
$O(n\log^2 n)$ rounds with high probability.
\end{theorem}

The proof of Theorem~\ref{thm:hop+lower-10p} is essentially the same as
that for Theorem \ref{thm:tri+lower-10p}, and is omitted.

\begin{theorem}[{\bf Lower bound for two-hop walk process}]
\label{thm:hop+lower-10p}
For any connected undirected graph $G$ that has $k \ge 1$ edges less
than the complete graph the two-hop process takes $\Omega(n \log
k)$ steps to complete with probability at least $1 - O\rb{e^{-k^{1/4}}}$.
\end{theorem}
